package leetcode.year2021.month12;

import leetcode.utils.ListNode;

import java.util.LinkedList;
//19. 删除链表的倒数第 N 个结点

/**
 * 解法一： 思路，使用栈先存储所有元素，然后删除末尾几个
 * 解法二： 双指针，第一个指针先向前走N步
 */
public class _04_1RemoveNthFromEnd19 {
  public static void main(String[] args) {
    ListNode listNode = new ListNode(new int[]{1, 2, 3, 4, 5});

    removeNthFromEnd(listNode,2);
  }
  public static ListNode removeNthFromEnd1(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode first = head;
    ListNode second = dummy;

    for (int i = 0; i < n; i++) {
      first = first.next;
    }
    while (first != null) {
      first = first.next;
      second = second.next;
    }

    second.next = second.next.next;
    return dummy.next;
  }

  public static ListNode removeNthFromEnd(ListNode head, int n) {

    ListNode dummy = new ListNode(0,head);

    ListNode prev = dummy;

    LinkedList<ListNode> stack = new LinkedList<>();

    while (prev != null){
      stack.addFirst(prev);
      prev = prev.next;
    }

    for (int i = 0; i < n; i++) {
      stack.removeFirst();
    }

    ListNode first = stack.getFirst();

    first.next = first.next.next;

    return dummy.next;
  }
  /**
   * 19. 删除链表的倒数第 N 个结点
   * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
   *
   *
   *
   * 示例 1：
   *
   *
   * 输入：head = [1,2,3,4,5], n = 2
   * 输出：[1,2,3,5]
   * 示例 2：
   *
   * 输入：head = [1], n = 1
   * 输出：[]
   * 示例 3：
   *
   * 输入：head = [1,2], n = 1
   * 输出：[1]
   *
   *
   * 提示：
   *
   * 链表中结点的数目为 sz
   * 1 <= sz <= 30
   * 0 <= Node.val <= 100
   * 1 <= n <= sz
   */
}
